package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class BubbleSort {

  public static void main(String[] args) {
    int[] arr = new int[80000];
    for (int i = 0; i < 80000; i++) {
      arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    }

    Date data1 = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String date1Str = simpleDateFormat.format(data1);
    System.out.println("排序前的时间是=" + date1Str);

    // 测试冒泡排序
    bubbleSort(arr);

    Date data2 = new Date();
    String date2Str = simpleDateFormat.format(data2);
    System.out.println("排序后的时间是=" + date2Str);

    // System.out.println("排序后");
    // System.out.println(Arrays.toString(arr));
  }

  // 将前面额冒泡排序算法，封装成一个方法
  public static void bubbleSort(int[] arr) {
    // 冒泡排序 的时间复杂度 O(n^2), 自己写出
    int temp = 0; // 临时变量
    boolean flag = false; // 标识变量，表示是否进行过交换
    // 外循环是轮数，每一轮将搜索范围内的最大值"换"到范围的最后面
    for (int i = 0; i < arr.length - 1; i++) {
      // 每一轮过后，搜索范围都会向前缩小一位
      for (int j = 0; j < arr.length - 1 - i; j++) { // 每次都从第一位开始找
        // 如果前面的数比后面的数大，则"交换"
        if (arr[j] > arr[j + 1]) { // 我们可以保证在j+1位置上一定是"目前"遇到的最大数
          flag = true;
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
      // System.out.println("第" + (i + 1) + "趟排序后的数组");
      // System.out.println(Arrays.toString(arr));

      if (!flag) { // 在一趟排序中，一次交换都没有发生过
        break;
      } else {
        flag = false; // 重置flag!!!, 进行下次判断
      }
    }
  }
}
